package java_core.two_array;

import java.util.ArrayList;
import java.util.List;

/*54. 螺旋矩阵https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode/
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4, 1],
[5, 6, 7, 8, 1],
[9,10,11,12, 1],
[9,10,11,12, 1]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]*/
public class SpiralMatrix {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>(matrix.length * matrix[0].length);
        for (int i = 0; i < matrix.length; i++) {
            if (i == 0) {

                for (int matrix1 : matrix[i]) {
                    list.add(matrix1);
                }

            } else {

            }

        }
        return null;
    }


    public List<Integer> spiralOrder2(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0) return ans;
        int R = matrix.length, C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < R * C; i++) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int cr = r + dr[di];
            int cc = c + dc[di];
            if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
                r = cr;
                c = cc;
            } else {
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;
    }

    public List<Integer> spiralOrder3(int[][] matrix) {

        if(matrix==null)
            return null;
        if(matrix.length==0)
            return new ArrayList<Integer>();


        int x=0,y=0;
        int pos = 1;//指示前进方向,1表示向右，2表示向下，3表示向左，4表示向上
        int bLeft = 0;//左边界
        int bRight=  matrix[0].length - 1;//右边界
        int bTop = 1;//上边界
        int bBottom = matrix.length - 1;//下边界

        int size = matrix.length * matrix[0].length;
        List<Integer> resList = new ArrayList<Integer>();
        for(int i=0;i<size;i++)
        {
            resList.add(matrix[x][y]);
            switch(pos)
            {
                case 1:
                    y++;
                    if(y>bRight)
                    {
                        //越过右边界
                        y = bRight;
                        x++;
                        bRight--;
                        pos = 2;
                    }
                    break;

                case 2:
                    x++;
                    if(x>bBottom)
                    {
                        //越过下边界
                        x = bBottom;
                        y--;
                        bBottom--;
                        pos = 3;
                    }
                    break;

                case 3:
                    y--;
                    if(y<bLeft)
                    {
                        //越过左边界
                        y = bLeft;
                        x--;
                        bLeft++;
                        pos=4;
                    }
                    break;

                case 4:
                    x--;
                    if(x<bTop)
                    {
                        //越过上边界
                        x = bTop;
                        y++;
                        bTop++;
                        pos = 1;
                    }
                    break;
            }
        }
        return resList;

    }



}
